import java.util.Deque;
import java.util.LinkedList;

/**
 * @description:
 * @Author: wuzhenbin
 * @CreateTime: 2025-02-13
 */
public class leetcode_53 {
    public static void main(String[] args) {
        System.out.println(maxSubArray1(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }

    public static int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        else if (nums.length == 1) return nums[0];
        int[][] dp = new int[nums.length][nums.length];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            dp[i][i] = nums[i];
            max = Math.max(dp[i][i], max);
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                dp[i][j] = dp[i][j - 1] + nums[j];
                max = Math.max(dp[i][j], max);
            }
        }
        return max;
    }

    public static int maxSubArray1(int[] nums) {
        if (nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        int tmp = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            //局部最大值
            tmp = Math.max(nums[i]+tmp,nums[i]);
            max = Math.max(tmp,max);
        }
        return tmp;
    }


}
